package com.tyrone.algorithm.priority;

import javax.print.DocFlavor;

/**
 * 最小索引优先队列
 * @param <T>
 */
public class IndexMinPriorityQueue<T extends Comparable<T>>{
    private T[] items ;     //用来存储元素的数组
    private int[] pq;       //保存每个元素在items数组中的索引，pq数组需要堆有序
    private int [] qp;      //保存qp的逆序，pq的值作为索引，pq的索引作为值
    private int N;          //记录堆中元素的个数

    public IndexMinPriorityQueue(int capacity){
        items=(T[])new Comparable[capacity+1];
        pq=new int[capacity+1];
        qp=new int[capacity+1];
        N=0;
        for (int i = 0; i < qp.length; i++) {
            qp[i]=-1;
        }
    }
    /**
     * 判断堆中索引i处的元素是否小于索引j处的元素
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i,int j){
        return items[pq[i]].compareTo(items[pq[j]])<0;
    }

    /**
     * 交换堆中i索引和j索引处的值
     * @param i
     * @param j
     */
    private void exch(int i,int j){
        int temp = pq[i];
        pq[i]=pq[j];
        pq[j]=temp;
        qp[pq[i]]=i;
        qp[pq[j]]=j;
    }

    /**
     * 删除队列中最小的元素,并返回该元素关联的索引
     * @return
     */
    public int delMin(){
        int minIndex = pq[1];
        exch(1,N);
        qp[pq[N]]=-1;
        pq[N]=-1;
        items[minIndex]=null;
        N--;
        sink(1);
        return minIndex;
    }

    /**
     * 往队列中插入一个元素,并关联索引i
     * @param i
     * @param t
     */
    public void insert(int i,T t){
        if (contains(i)){
            throw new RuntimeException("索引已经存在");
        }
        N++;
        items[i]=t;
        pq[N]=i;
        qp[i]=N;
        swim(N);
    }

    /**
     * 使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
     * @param k
     */
    private void swim(int k){
        while(k>1){
            if (less(k,k/2)){
                exch(k,k/2);
            }
            k/=2;
        }
    }

    /**
     * 使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
     * @param k
     */
    private void sink(int k){
        while (2*k<=N){
            int min=2*k;
            if (2*k+1<=N){
                if (less(2*k+1,2*k)){
                    min=2*k+1;
                }
            }
            if (less(k,min)){
                break;
            }
            exch(k,min);
            k=min;
        }
    }

    /**
     * 获取队列中元素的个数
     * @return
     */
    public int size(){
        return N;
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty(){
        return N==0;
    }

    /**
     * 判断k对应的元素是否存在
     * @param k
     * @return
     */
    public boolean contains(int k){
        return qp[k]!=-1;
    }

    /**
     * 把与索引i关联的元素修改为为t
     * @param i
     * @param t
     */
    public void changeItem(int i, T t){
        items[i]=t;
        int k = qp[i];
        sink(k);
        swim(k);
    }

    /**
     * 最小元素关联的索引
     * @return
     */
    public int minIndex(){
        return pq[1];
    }

    /**
     * 删除索引i关联的元素
     * @param i
     */
    public void delete(int i){
        int k = qp[i];
        exch(k,N);
        qp[pq[N]] = -1;
        pq[N]=-1;
        items[i]=null;
        N--;
        sink(k);
        swim(k);
    }



}
